package own.stu.jobgib.playown.alg.solution.sort;

public class MergeSort {

    public static void main(String[] args) {
        MergeSort s = new MergeSort();

        /*int[] nums = {6, 3, 5, 76, 2, 3, 0, 2, 42};

        s.mergeSort(nums);
        for (int num : nums) {
            System.out.print(num + ", ");
        }
        System.out.println();*/

//        System.out.println(s.reversePairs(new int[]{1, 3, 2, 3, 1}));
//        System.out.println(s.reversePairs(new int[]{3, 5, 8, 1, 2, 3}));
        System.out.println(s.reversePairs(new int[]{2, 4, 3, 5, 1}));
    }

    /**
     * 493. 翻转对
     * 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
     * 你需要返回给定数组中的重要翻转对的数量。
     * <p>
     * 示例 1:
     * 输入: [1,3,2,3,1]
     * 输出: 2
     * <p>
     * 3 5 8 , 1 2 3 两个已排序的数组（merge sort）中 的 翻转对
     * 1 + 2 + 3 = 6个
     */
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        mergeSort(nums, 0, nums.length - 1);
        return cnt;
    }

    int cnt = 0;

    private void reversePairsMerge(int[] nums, int lStart, int mid, int rEnd) {
        int lEnd = mid, rStart = mid + 1;
        int len = rEnd - lStart + 1;

        int i = lStart, j = rStart;
        for (; i <= lEnd; i++) {
            while (j <= rEnd && (long) nums[i] > 2 * (long) nums[j]) {
                j++;
            }
            cnt += j - rStart;
        }

        int[] tmp = new int[len];
        i = lStart;
        j = rStart;
        int k = 0;
        while (i <= lEnd && j <= rEnd) {
            if (nums[i] < nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }

        while (i <= lEnd) {
            tmp[k++] = nums[i++];
        }
        while (j <= rEnd) {
            tmp[k++] = nums[j++];
        }

        i = lStart;
        for (k = 0; k < len; k++) {
            nums[i++] = tmp[k];
        }
    }

    /**
     * mergeSort pure
     *
     * @param nums
     */
    public void mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
    }

    private void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        // merge(nums, l, mid, r);
        reversePairsMerge(nums, l, mid, r);
    }

    private void merge(int[] nums, int lStart, int mid, int rEnd) {
        int lEnd = mid, rStart = mid + 1;
        int len = rEnd - lStart + 1;
        int[] tmp = new int[len];
        int i = lStart, j = rStart, k = 0;
        while (i <= lEnd && j <= rEnd) {
            if (nums[i] < nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }

        while (i <= lEnd) {
            tmp[k++] = nums[i++];
        }
        while (j <= rEnd) {
            tmp[k++] = nums[j++];
        }

        i = lStart;
        for (k = 0; k < len; k++) {
            nums[i++] = tmp[k];
        }
    }
}
